COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a13.tex[106,phy] \today\hfill}

\bigskip

{\rmn
{\narrower\smallskip\noindent
{\bf Exercise:} ``Arithmetic'' on irrational numbers.
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent
Let the number $a+b\sqrt{5}$, where $a$ and $b$ are integers, be represented
by a pair of integer variables {\tt A} and~{\tt B}, where {\tt A} 
and~{\tt B} contain $a$ and~$b$ respectively.
Write a program to compute $(\sqrt{5}-1)↑{10}$ exactly, i.e., to print
integers $c$ and $d$ such that $(\sqrt{5}-1)↑{10}=c+d\sqrt{5}$ exactly.
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent
{\bf Hint:} design a subalgorithm to multiply two such numbers exactly,
using the identity 
$$(a+b\sqrt{5}\,)(c+d\sqrt{5}\,)=(ac+5bd)+(ad+bc)\sqrt{5}\,.$$
\smallskip}
}

{\rmn
{\narrower\smallskip\noindent
{\bf Solution:}
\smallskip}
}

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        A:=1, B:=0 (* 1+0*SQRT 5 *);
        FOR J:=1 TO 10 DO
           BEGIN
           (* (A+B*SQRT(5))*(-1+1*SQRT(5))=(-A+5*B)+(A-B)*SQRT(5) *)
           C:=5*B-A; D:=A-B;
           A:=C; B:=D (* REPRESENTING (C+D*SQRT(5)) TO POWER J *)
           END
        WRITE (A,'+',B,'*SQRT(5)')
}

\bigskip
{\rmn
{\narrower\smallskip\noindent
{\bf Exercise:} 
Write a program to find $(\sqrt{2}-1)↑{16}$ exactly by successive squarings.
See previous exercise for suggestions. If the answer is $C+D\sqrt{2}$,
how different is $-C/D$ from~$\sqrt{2}\;$?
\smallskip}
}

\vfill\eject

%\bigskip
\line{\bf SAMPLE SOLUTION TO ASSIGNMENT \# 4\hfil}

\smallskip
{\obeylines\obeyspaces\let =\ \tt
        program ExactExpressions(input,output);

\smallskip
(*****************************************************************
This program calculates the first 10 powers of the expression
         
               (A + B * SQRT(5)) 
   
giving the results in terms of integer values and SQRT(5)
[RWF: redo interactive IO]
*****************************************************************)
   
\smallskip
           var A, B, C, D, SaveC : integer;
              Count : integer;
   
        begin  (* Exact Expressions *)
   
           (* Input *)
           write('Enter coefficients A and B separated by a space: ');
           read(A,B);
           writeln; writeln;
\smallskip
           (* Initialization *)
           C:= A; D:= B;
\smallskip
           (* Calculations and Output *)
           for Count:= 1 to 10 do begin
              writeln(C:10,' + ',D:10,' * SQRT(5)');
              SaveC:= C;
              C:= A*C + 5*B*D;
              D:= A*D + SaveC*B;
           end;
\smallskip
        end.   (* ExactExpressions *)
}

\medskip
{\obeylines\obeyspaces\let =\ \tt
        @exec exact
        Stanford LOTS/Passgo 20 [EXACTE] -- 1.. 
        Runtime:   0: 0.185
        [EXACTE execution]
        INPUT      : tty:
        OUTPUT     : tty:
        [INPUT, end with $\uparrow$Z: ]
\smallskip
        Enter coefficients A and B separated by a space: 3 1
\smallskip

              3 +          1 * SQRT(5)
             14 +          6 * SQRT(5)
             72 +         32 * SQRT(5)
            376 +        168 * SQRT(5)
           1968 +        880 * SQRT(5)
          10304 +       4608 * SQRT(5)
          53952 +      24128 * SQRT(5)
         282496 +     126336 * SQRT(5)
        1479168 +     661504 * SQRT(5)
        7745024 +    3463680 * SQRT(5)
}


\bigskip
\line{\copyright 1984 Robert W. Floyd; 
First draft (not published) March 29, 1984\hfil}
First draft July 19, 1984
%revised: Date; subsequently revised.\hfill}

\bye